package cn.bellychang.leetcode.question160;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ChangLiang
 * @date 2021/2/8
 */
public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        Deque<ListNode> stackA = new ArrayDeque<>();
        Deque<ListNode> stackB = new ArrayDeque<>();

        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }

        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }

        int min = Math.min(stackA.size(), stackB.size());

        ListNode result = null;

        while (min != 0) {
            ListNode pollA = stackA.pop();
            ListNode pollB = stackB.pop();
            if (pollA.equals(pollB)) {
                result = pollA;
            } else {
                return result;
            }
            min--;
        }
        return result;
    }
}
